Pumping Lemma Example 2

1. We don't know m, but assume there is one.

2. Choose a string w = aⁿb^k where n > m, so that any prefix of length m consists entirely of a's, and k = n-1, so that there is just one more a than b.

3. We don't know the decomposition of w into xyz, but since |xy| m, xy must consist entirely of a's. Moreover, y cannot be empty.

4. Choose i = 0. This has the effect of dropping |y| a's out of the string, without affecting the number of b's. The resultant string has fewer a's than before, so it has either fewer a's than b's, or the same number of each. Either way, the string does not belong to L, so L is not regular.